package com.dexter.year2023.charpter1_linkedlist.level2.topic2_4双指针;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 面试题 02.02. 返回倒数第 k 个结点
 * https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/
 * <p>
 * 实现一种算法，找出单向链表中倒数第 k 个结点。返回该结点的值。
 * 注意：本题相对原题稍作改动
 * <p>
 * 示例：
 * 输入： 1->2->3->4->5 和 k = 2
 * 输出： 4
 * <p>
 * 说明：
 * 给定的 k 保证是有效的。
 *
 * @author Dexter
 */
public class Demo2GetKthFromEnd {
    public static void main(String[] args) {
        int[] a = {1, 2, 3, 4, 5};
        Node head = initLinkedList(a);
        int k = 2;

        // 本节方法，定义快慢指针
        head = getKthFromEnd(head, k);
        printLinkedList(head);
    }

    /**
     * 快指针 k+1 位置，与慢指针相隔 k 步，那么一起同步时，快指针在尾结点，慢指针在倒数第k个位置，return即可
     *
     * @param head
     * @param k
     * @return
     */
    private static Node getKthFromEnd(Node head, int k) {
        Node slow = head, fast = head;
        while (fast != null && k > 0) {
            fast = fast.next;
            k--;
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
